import java.util.ArrayList;
import java.util.List;

public class Subsets {
    static  List<Integer> path = new ArrayList<Integer>();
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public static  List<List<Integer>> subsets(int[] nums) {
        dfs1(0, nums);
        return ans;
    }

    /**
     *
     * @param startIndex  从哪里取数,告诉我们下一次递归从哪开始取数
     * @param nums
     *          []
     *  [1]    [2]      [3]
     * [2,3]   [3]
     * [3]
     * 收获这棵树的所有节点
     * */
    public static void dfs1(int startIndex,int[] nums){
        /**
         * 每次进入递归，就要把当前路径收获到的结果收集起来
         */
        ans.add(new ArrayList<>(path));
        if (startIndex >= nums.length){
            return;
        }
        //单层搜索逻辑.横向的取数
        for (int i = startIndex ;i < nums.length ; i++){
            // 纵方向，路径，收获元素
            path.add(nums[i]);
            //收获结果，进行下一层递归
            //通过控制startIndex,那下一层递归就只能从后面开始取数了
            dfs1(i+1,nums);
            //回溯，把刚刚加进去的数据弹出去，才能把另一个选择加进来
            path.remove(path.size()-1);
        }

    }
    public static  void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }
        //考虑选择当前位置
        path.add(nums[cur]);
        dfs(cur + 1, nums);
        //考虑不选择当前位置
        path.remove(path.size() - 1);
        dfs(cur + 1, nums);
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> list = subsets(nums);
    }
}
